home *** CD-ROM | disk | FTP | other *** search
/ The 640 MEG Shareware Studio 2 / The 640 Meg Shareware Studio CD-ROM Volume II (Data Express)(1993).ISO / clang / jcool01.zip / QUEUE.C < prev    next >
C/C++ Source or Header  |  1992-09-29  |  13KB  |  418 lines
  1. //
  2. // Copyright (C) 1991 Texas Instruments Incorporated.
  3. //
  4. // Permission is granted to any individual or institution to use, copy, modify,
  5. // and distribute this software, provided that this complete copyright and
  6. // permission notice is maintained, intact, in all copies and supporting
  7. // documentation.
  8. //
  9. // Texas Instruments Incorporated provides this software "as is" without
  10. // express or implied warranty.
  11. //
  12. // Updated: JAM 09/23/92 -- added def and init for compare_s
  13.  
  14. #include <cool/Queue.h>
  15.  
  16. // compare_s -- Pointer operator== function
  17. template<class Type> 
  18. Boolean (*CoolQueue<Type>::compare_s)(const Type&, const Type&) = CoolQueue_is_data_equal;
  19.  
  20. // CoolQueue<Type> () -- Empty constructor for the CoolQueue class
  21. // Input:            None
  22. // Output:           None
  23.  
  24. template<class Type> 
  25. CoolQueue<Type>::CoolQueue() {
  26.   this->data = NULL;                // Intialize data
  27. }
  28.  
  29.  
  30. // CoolQueue<Type> (unsigned int) -- constructor that specifies number of elements
  31. // Input:                Integer number of elements
  32. // Output:               None
  33.  
  34. template<class Type> 
  35. CoolQueue<Type>::CoolQueue(unsigned int n)
  36.  : CoolBase_Queue(n)
  37. {
  38.   this->data = (Type*) new Type[n];        // Allocate memory
  39. }
  40.  
  41.  
  42. // CoolQueue<Type> (void*, int) -- constructor that specifies user-defined storage
  43. //                              and number of elements
  44. // Input:                       Integer number of elements
  45. // Output:                      None
  46.  
  47. template<class Type> 
  48. CoolQueue<Type>::CoolQueue(void* s, unsigned int n)
  49.  : CoolBase_Queue(n)
  50. {
  51.   this->data = (Type*) s;            // Pointer to storage
  52.   this->alloc_size = INVALID;            // Indicate this is static size
  53. }
  54.  
  55.  
  56. // CoolQueue<Type> (CoolQueue<Type>&) -- Copy constructor
  57. // Input:                        CoolQueue reference
  58. // Output:                       None
  59.  
  60. template<class Type> 
  61. CoolQueue<Type>::CoolQueue(const CoolQueue<Type>& s)
  62.  : CoolBase_Queue(s)
  63. {
  64.   this->data = (Type*) new Type[s.limit];    // New memory allocation
  65.   for (int i = 0; i < s.limit; i++)        // For each element
  66.     this->data[i] = s.data[i];            // Copy data into this
  67. }
  68.  
  69.  
  70. // ~CoolQueue<Type> -- Destructor for CoolQueue class that frees up storage
  71. // Input:          None
  72. // Output:         None
  73.  
  74. template<class Type> 
  75. CoolQueue<Type>::~CoolQueue() {
  76.   if (this->limit != 0 &&
  77.       this->alloc_size != INVALID)        // If not static-size object
  78.     delete [] this->data;            // Free up the memory
  79. }
  80.  
  81.  
  82.  
  83. // Type& get () -- Get and remove first-in item in this CoolQueue
  84. // Input:          None
  85. // Output:         Reference to first-in Type value
  86.  
  87. template<class Type> 
  88. Type& CoolQueue<Type>::get () {
  89. #if ERROR_CHECKING
  90.   if (in == out) {                // If no elements in CoolQueue
  91.     printf ("CoolQueue<%s>::get(): No elements in queue.\n", #Type);
  92.     abort ();
  93.   }
  94. #endif
  95.   int result = out;                // Get data
  96.   if (++out >= limit) out = 0;            // increment and wrap
  97.   return data[result];
  98. }
  99.  
  100. // Boolean get (Type& result) -- Get and remove first-in item in this CoolQueue
  101. // Input:          None
  102. // Output:         Reference to first-in Type value
  103.  
  104. template<class Type>
  105. Boolean CoolQueue<Type>::get (Type& result) {
  106.   if (in == out) return FALSE;
  107.   result = this->data[out];        // Get data
  108.   if (++out >= limit) out = 0;        // Increment and wrap
  109.   return TRUE;
  110. }
  111.  
  112. // Boolean unget (Type&) -- Return TRUE if able to put a Type value on the
  113. //                          front-end of this CoolQueue
  114. // Input:                   Reference to a Type value
  115. // Output:                  TRUE or FALSE
  116.  
  117. template<class Type> 
  118. Boolean CoolQueue<Type>::unget (const Type& value) {
  119.   int save = out;
  120.   if (--out < 0) out = limit - 1;    // decrement and wrap
  121.   if (in == out) {            // Check for full
  122.     out = save;
  123.     if (!this->grow()) return FALSE;
  124.     if (--out < 0) out = limit - 1;    // decrement and wrap
  125.   }
  126.   data[out] = value;            // Stuff data
  127.   return TRUE;
  128. }
  129.  
  130. // Boolean put (Type&) -- Put a new last-in item on this CoolQueue; return TRUE
  131. ///                       if successful
  132. // Input:                 Reference to a Type value
  133. // Output:                TRUE or FALSE
  134.  
  135. template<class Type> 
  136. Boolean CoolQueue<Type>::put (const Type& value) {
  137.   int save = in;
  138.   if (++in >= limit) in = 0;        // Increment and Wrap
  139.   if (in == out) {            // Check for full
  140.     in = save;
  141.     if (!this->grow()) return FALSE;
  142.     save = in;
  143.     if (++in >= limit) in = 0;        // Increment and Wrap
  144.   }
  145.   data[save] = value;            // Store
  146.   curpos = in;                // Invalidate curpos
  147.   return TRUE;
  148. }
  149.  
  150. // Type& unput () -- Remove and return last-in item of this CoolQueue
  151. // Input:            None
  152. // Output:           Reference to the Type value of the last-in item
  153.  
  154. template<class Type> 
  155. Type& CoolQueue<Type>::unput () {
  156. #if ERROR_CHECKING
  157.   if (in == out) {                // If no elements in queue
  158.     printf ("CoolQueue<%s>::unput(): No elements in queue.\n", #Type);
  159.     abort ();
  160.   }
  161. #endif
  162.   if (--in < 0) in = limit - 1;            // decrement and wrap
  163.   curpos = in;                    // Invalidate curpos
  164.   return data[in];
  165. }
  166.  
  167. template<class Type>
  168. Boolean CoolQueue<Type>::unput (Type& result) {
  169.   if (in == out) return FALSE;            // If no elements in queue
  170.   if (--in < 0) in = limit - 1;            // decrement and wrap
  171.   curpos = in;                    // Invalidate curpos
  172.   result = this->data[in];                // Get data
  173.   return TRUE;
  174. }
  175.  
  176. // Boolean find (Type&) -- Return TRUE if value is found in this CoolQueue
  177. // Input:                  Reference to a Type value
  178. // Output:                 TRUE or FALSE
  179.  
  180. template<class Type> 
  181. Boolean CoolQueue<Type>::find (const Type& value) {
  182.   int i;
  183.   if (in == out)                // Nothing is in CoolQueue
  184.     return FALSE;                // Return failure
  185.   if (in > out) {
  186.     for (i = out; i < in; i++)            // check from out to in-1
  187.       if ((*(this->compare_s))(this->data[i], value)) { // If found
  188.         this->curpos = i;            // Set curpos to index 
  189.         return TRUE;                // Return success
  190.       }
  191.   }
  192.   else {
  193.     for (i = out; i < limit; i++)        // check from out to limit-1
  194.       if ((*(this->compare_s))(this->data[i], value)) { // If found
  195.         this->curpos = i;            // Set curpos to index 
  196.         return TRUE;                // Return success
  197.       }
  198.     for (i = 0; i < in; i++)            // check from first to in-1
  199.       if ((*(this->compare_s))(this->data[i], value)) { // If found
  200.         this->curpos = i;            // Set curpos to index 
  201.         return TRUE;                // Return success
  202.       }
  203.   }
  204.   return FALSE;                    // Return failure
  205. }
  206.  
  207. template<class Type> 
  208. Boolean CoolQueue<Type>::grow () {
  209.   int new_size;
  210.   if (this->alloc_size == INVALID) return FALSE;
  211.   if (growth_ratio_s > 0.0)
  212.      new_size = (int)(limit * (1.0 + growth_ratio_s)); // New size?
  213.   else
  214.     new_size = limit + alloc_size;
  215.   resize(new_size);
  216.   return TRUE;
  217. }
  218.   
  219.  
  220. // void resize (int)-- Adjust the memory size of a CoolQueue to accomodate some
  221. //                      new size
  222. // Input:               Number of elements to hold
  223. // Output:              None
  224.  
  225. template<class Type> 
  226. void CoolQueue<Type>::resize (int s) {
  227. #if ERROR_CHECKING
  228.   if (this->alloc_size == INVALID) {        // If not allowed to grow
  229.     this->resize_error (#Type);            // Raise exception
  230.     return;                    // Return
  231.   }
  232. #endif
  233.   Type* temp;                    // Temporary variable
  234.   Type* tp;
  235.   int len = this->length();
  236.   int i;
  237.   tp = temp = (Type*) new Type[s];        // Allocate storage
  238.   if (in > out) {
  239.     for (i = out; i < in; i++)            // copy from out to in-1
  240.       *tp++ = data[i];                // Copy value
  241.   }
  242.   if (in < out) {
  243.     for (i = out; i < limit; i++)        // copy from out to limit-1
  244.       *tp++ = data[i];                // Copy value
  245.     for (i = 0; i < in; i++)            // copy from first to in-1
  246.       *tp++ = data[i];                // Copy value
  247.   }
  248.   if (this->limit != 0)
  249.     delete [] this->data;            // Free up old memory
  250.   this->data = temp;                // Assign new memory block
  251.   this->limit = s;                // Save new size value
  252.   curpos = len;
  253.   in = len;
  254.   out = 0;
  255. }
  256.  
  257.  
  258. // Boolean remove () -- Destructively remove item at current position; return
  259. //                      TRUE if successful
  260. // Input:               None
  261. // Output:              TRUE or FALSE
  262. template<class Type> 
  263. Boolean CoolQueue<Type>::remove () {
  264.   int i;
  265.   if (in == out) return FALSE;            // Fail if nothing in queue
  266.   if (in > out) {                // Data is between out and in-1
  267.     if (curpos < out || curpos >= in)        // Fail if invalid curpos
  268.       return FALSE;
  269.     in--;
  270.     for (i = curpos; i < in; i++)
  271.       data[i] = data[i+1];
  272.   }                           
  273.   else {
  274.     if (curpos >= out) {               // Data is between out and limit
  275.       if (curpos >= limit)               // fail if invalid curpos
  276.     return FALSE;
  277.       out--;
  278.       for (i = curpos; i >= out; i--)
  279.     data[i] = data[i - 1];
  280.     }
  281.     else {                        // data is between 0 and in-1
  282.       if (curpos >= in)                   // fail if invalid curpos
  283.     return FALSE;
  284.       in--;
  285.       for (i = curpos; i < in; i++)
  286.     data[i] = data[i+1];
  287.     }
  288.   }
  289.   return TRUE;                    // Report success
  290. }
  291.  
  292.  
  293. // Boolean remove (Type&) -- Destructively remove the first occurence of an 
  294. //                           element, starting from front of this CoolQueue; return
  295. //                           TRUE if element is found and removed
  296. // Input:                    Reference to Type value
  297. // Output:                   TRUE or FALSE
  298.  
  299. template<class Type> 
  300. Boolean CoolQueue<Type>::remove (const Type& value) {
  301.  return find(value) && remove();    // find it, Remove it & return status
  302. }
  303.  
  304.  
  305. // CoolQueue<Type>& operator= (CoolQueue<Type>&) -- Assignment
  306. // Input:  Reference to a CoolQueue
  307. // Output: Reference to modified this
  308.  
  309. template<class Type> 
  310. CoolQueue<Type>& CoolQueue<Type>::operator= (const CoolQueue<Type>& s) {
  311.   if (this != &s) {
  312.     int len = s.length();
  313.     int i;
  314.     if (this->limit < len) {            // if not enough memory
  315. #if ERROR_CHECKING
  316.       if (this->alloc_size == INVALID)        // If static size queue
  317.     this->assign_error (#Type);        // Raise exception
  318. #endif
  319.       if (this->limit != 0)
  320.     delete [] this->data;                    // Free it up
  321.       this->limit = s.limit;            // New CoolQueue size
  322.       this->data = (Type*) new Type[s.limit];    // Allocate bigger memory
  323.     }
  324.     out = 0;
  325.     in = len;
  326.     curpos = len;
  327.     register Type* dp = this->data;
  328.     if (s.in >= s.out)
  329.       for (i = s.out; i < s.in; i++)        // copy from s.out to s.in-1
  330.     *dp++ = s.data[i];            // Copy value
  331.     else {
  332.       for (i = s.out; i < s.limit; i++)        // copy from s.out to s.limit-1
  333.     *dp++ = s.data[i];            // Copy value
  334.       for (i = 0; i < s.in; i++)        // copy from first to s.in-1
  335.     *dp++ = s.data[i];            // Copy value
  336.     }}
  337.   return *this;                    // Return reference
  338. }
  339.  
  340.  
  341. // Boolean operator== (CoolQueue<Type>&) -- Compare this CoolQueue with another
  342. //                                      CoolQueue;
  343. // Input:  Reference to a CoolQueue
  344. // Output: TRUE or FALSE if equal/non equal.
  345.  
  346. template<class Type> 
  347. Boolean CoolQueue<Type>::operator== (const CoolQueue<Type>& q) const {
  348.   if (this->length() != q.length())        // If not same number
  349.     return FALSE;                // Then not equal
  350.   int tp = this->out;
  351.   int qp = q.out;
  352.       while (tp != this->in) {
  353.     if (!(*this->compare_s)(this->data[tp], q.data[qp]))
  354.       return FALSE;                // Return failure if no match
  355.     if (++tp >= this->limit) tp = 0;        // increment and wrap
  356.     if (++qp >= q.limit) tp = 0;        // increment and wrap
  357.   }
  358.   return TRUE;
  359. }
  360.  
  361.  
  362. // Boolean is_data_equal -- Default data comparison function if user has not
  363. //                          provided another one.
  364. // Input:                   Two Type references
  365. // Output:                  TRUE or FALSE
  366.  
  367. template<class Type>
  368. Boolean CoolQueue_is_data_equal (const Type& t1, const Type& t2) {
  369.    return (t1 == t2);
  370. }
  371.  
  372.  
  373. // void set_compare(Compare) -- Set this CoolQueue's compare function
  374. // Input:  Pointer to a compare function
  375. // Output: None
  376.  
  377. template<class Type> 
  378. void CoolQueue<Type>::set_compare (Boolean (*cf) (const Type&, const Type&)) {
  379.   if (cf == NULL)
  380.     this->compare_s = &CoolQueue_is_data_equal; // Default equality function
  381.   else
  382.     this->compare_s = cf;            // Else set to user function
  383. }
  384.  
  385.  
  386. // operator<< -- Overload the output operator for CoolQueue
  387. // Input:        ostream reference, queue reference
  388. // Output:       CoolQueue data is output to ostream
  389.  
  390. template<class Type>
  391. ostream& operator<< (ostream& os, const CoolQueue<Type>& q) {
  392.   return q.qprint(os);
  393. }
  394.  
  395.  
  396. // This is a method because Glockenspiel's Cfront 1.2 doesn't let 
  397. // friend functions access the protected data members of our base class
  398. template<class Type>
  399. ostream& CoolQueue<Type>::qprint(ostream& os) const {
  400.   if (in == out)                // If no elements
  401.     os << " Empty ";                // Report empty status
  402.   else {
  403.     int i;
  404.     os << "[ ";
  405.     if (in >= out)
  406.       for (i = out; i < in; i++)        // copy from out to in-1
  407.     os << data[i] << " ";
  408.     else {
  409.       for (i = out; i < limit; i++)        // copy from out to limit-1
  410.     os << data[i] << " ";
  411.       for (i = 0; i < in; i++)            // copy from first to in-1
  412.     os << data[i] << " ";
  413.     }
  414.     os << "]";
  415.   }
  416.   return os;                    // Return stream reference
  417. }
  418.